package QuestionDaily;

import utils.TreeNode;

import java.util.*;

public class pseudoPalindromicPaths_1457 {
    /**
     * 二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
     * @param root 每个节点的值为 1 到 9
     * @return 返回从根到叶子节点的所有路径中 伪回文 路径的数目
     */
    //第一种写法，直接超时
//    public int pseudoPalindromicPaths (TreeNode root) {
//        int count=0;
//        path.push(root.val);
//        if(root.left==null&&root.right==null)
//            return pseudoPalindromic(path)?1:0;
//        if (root.left != null) {
//            count += pseudoPalindromicPaths(root.left);
//            path.pop();
//        }
//        if (root.right != null) {
//            count += pseudoPalindromicPaths(root.right);
//            path.pop();
//        }
//        return  count;
//    }
//    Stack<Integer> path=new Stack<>();
//
//    /**
//     * 判定是否是伪回文
//     */
//    boolean pseudoPalindromic(Stack<Integer> path){
//        /**
//         * 伪回文，所有数字都是偶数个，可以存在一个奇数个的数字
//         */
//        int[]num=new int[9];
//        for (int i:path){
//            num[i-1]++;
//        }
//        boolean flag=false; //是否已经有了奇数个的数字
//        for (int i : num) {
//            if (i % 2 != 0) {
//                if (flag == false)
//                    flag = true;
//                else
//                    return false;
//            }
//        }
//        return true;
//    }
//
    public int pseudoPalindromicPaths (TreeNode root) {
        /**
         * 递归加上动态规划
         * 11ms 58%
         */
        int[]num=new int[9];
        return  dfs(root,num);
    }
    int dfs(TreeNode root, int[]num){
        int count=0;
        num[root.val-1]++; //进入该层递归，递归对应数字数量加1
        if(root.left==null&&root.right==null){
            boolean flag=pseudoPalindromic(num);
            num[root.val-1]--; //退出该层递归，对应数字数量减1
            return flag?1:0;
        }
        if (root.left != null) {
            count += dfs(root.left,num);
        }
        if (root.right != null)
            count += dfs(root.right,num);
        num[root.val-1]--; //退出该层递归，对应数字数量减1
        return  count;
    }
    /**
     * 判定是否是伪回文
     */
    boolean pseudoPalindromic( int[]num){
        /**
         * 伪回文，只存在一个奇数个的数字
         */
        boolean flag=false; //是否已经有了奇数个的数字
        for (int i : num) {
            if (i % 2 != 0) {
                if (flag == false)
                    flag = true;
                else
                    return false;
            }
        }
        return true;
    }


    /**
     * 高解，位运算
     * 2ms
     */
    public int pseudoPalindromicPaths2 (TreeNode root) {
        if (root == null) return 0;
        int nums = 0;
        dfs(root, nums);
        return ans;
    }
    int ans = 0;
    public void dfs(TreeNode root, int temp) {
        int n = temp ^ (1 << root.val);  // 把1向右移动var个位置， 把个数就存到对应大小的位置，再进行异或，如果偶数个该位最终就是0，否则是1
        if (root.left == null && root.right == null) {
            if (n == 0 || (n & (n - 1)) == 0) { //n & (n - 1) 可以用来消除最后一个1
                ++ans;
            }
            return;
        }
        if (root.left != null) {
            dfs(root.left, n);
        }
        if (root.right != null) {
            dfs(root.right, n);
        }
    }
}
